import static java.lang.String.format;

/**
 * Date: 2023-04-20
 * Time: 8:11
 */
public class DoubleList {

    static class Node {
        Node prev;

        int value;

        Node next;

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    private Node head;//头哨兵
    private Node tail;//尾哨兵

        public DoubleList(){
            head = new Node(null, 666, null);
            tail = new Node(null, 666, null);
            head.next = tail;
            tail.prev = head;
        }

    // 尾增
    public void addLast(int value){
            Node prev = tail.prev;
            Node node = new Node(prev,value,tail);
            prev.next = node;
            tail.prev = node;
    }

    // 根据索引删除元素
    public void remove(int index){
            Node prev = findNode(index-1);
            if(prev == null){
                IllegalAccessException(index);
            }
            Node next = findNode(index+1);

            prev.next = next;
            next.prev = prev;
        }

    // 根据索引查找节点
    public Node findNode(int index) {
        int i = -1;
        for (Node p = head; p != tail; p = p.next, i++) {
            if (index == i) {
                return p;
            }
        }
        return null;
    }

    // 根据索引插入值
    public void insert(int index,int value){

        Node prev = findNode(index-1);
        if(prev == null){
            IllegalAccessException(index);
        }
        Node next = findNode(index+1);

        Node node = new Node(prev,value,next);

        prev.next = node;
        next.prev = node;
    }

    public void addFirst(int value){
            insert(0,value);
    }

    public void IllegalAccessException(int index){
        try {
            throw new IllegalAccessException(format("index[ %d ]不合法%n",index));
        } catch (IllegalAccessException e) {
            throw new RuntimeException(e);
        }
    }

}


